# koroFileHeader at Yungoal acer
# Create: 2021-09-07 09:40:31
# LastEdit: 2021-09-07 10:01:16
"""https://leetcode-cn.com/problems/climbing-stairs/"""
__author__ = '749B'


import functools

class Solution:

    @functools.lru_cache()
    def climbStairs(self, n: int) -> int:
        """递归"""
        if n == 1 or n == 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n -2)

    def climbStairs2(self, n: int) -> int:
        """本质上就是个斐波那契数列"""
        b1, b2 = 1, 1
        for _ in range(n - 1):
            b1, b2 = b2, b1 + b2
        return b2
